#include<iostream>
using namespace std;
#include<vector>
#include<unordered_map>
#include<string>

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        auto lambda1 = [](char c) -> int {return (c == '7' || c == '9') ? 4 : 3;};
        unordered_map<int, string> um = {
            {1, ""}, {2, "abc"}, {3, "def"}, {4, "ghi"},
            {5, "jkl"}, {6, "mno"}, {7, "pqrs"}, {8, "tuv"}, {9, "wxyz"}
        };

        //计算当前字符串的可能性数量
        int possible = 1;
        for(int i = 0; i < digits.size(); ++i){
            possible *= lambda1(digits[i]);
        }
        vector<string> ret;
        if(digits == "") return ret;
        ret.resize(possible);

        //安插法
        int sub_len = possible / lambda1(digits[0]);
        for(int i = 0; i < digits.size(); ++i){
            int num = digits[i] - '0';
            //用来遍历digits 从而插入到ret中
            for(int j = 0; j < possible; ++j){
                //对ret中的每一个string插入
                ret[j] += (um[num])[j / sub_len % lambda1(digits[i])];
                //j / sub_len算出来当前在sub_len长度为一组的情况下，处于第几组
                //然后再取余当前遍历到的数字对应的字符串长度，获取到当前应该插入哪个字母
            }
            if(i <= digits.size() - 1) sub_len /= lambda1(digits[i + 1]);
        }
        return ret;
    }
};
